Level set methods have become increasingly popular as a framework for image segmentation.
The level set method was introduced by Osher and Sethian as a means to implicitly propagate hypersurfaces C(t) in a domain Ω⊂Rn by evolving an appropriate embedding function or level set function φ: Ω×[0,T]→R, where:C(t)={xεΩ|φ(x,t)=0}.  (1)
See S. J. Osher and J. A. Sethian: Fronts propagation with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations: J. of Comp. Phys., 79: 12-49, 1988.
The ordinary differential equation propagating explicit boundary points is replaced by a partial differential equation modeling the evolution of a higher-dimensional embedding function.1 Advantages of this approach are well-known: firstly, the implicit boundary representation does not depend on a specific parameterization, and no control point regriding mechanisms need to be introduced during the propagation. Secondly, evolving the embedding function allows topological changes to be modeled elegantly, such as splitting and merging of the embedded boundary. Thirdly, the implicit representation (1) naturally generalizes to hypersurfaces in three or more dimensions. To impose a unique correspondence between a contour and its embedding function one can constrain φ to be a signed distance function, i.e. |∇φ|=1 almost everywhere.
A precursor of the level set method was proposed by Dervieux and Thomasset. See A. Dervieux and F. Thomasset: A finite element method for the simulation of Raleigh-Taylor instability: Springer Lect. Notes in Math., 771:145-158, 1979.
Early applications of the level set method to image segmentation were disclosed by Malladi et al., by Caselles et al., by Kichenassamy et al., and by Paragios and Deriche. See R. Malladi, J. A. Sethian, and B. C. Vemuri: A topology independent shape modeling scheme: In SPIE Conf. on GeometricMethods in Comp. Vision II, volume 2031, pages 246-258, 1994; V. Caselles, R. Kimmel, and G. Sapiro: Geodesic active contours: In Proc. IEEE Intl. Conf. on Comp. Vis., pages 694-699, Boston, USA, 1995; S. Kichenassamy, A. Kumar, P. J. Olver, A. Tannenbaum and A. J. Yezzi: Gradient flows and geometric active contour models: In IEEE Intl. Conf. on Comp. Vis., pages 810-815, 1995; and N. Paragios and R. Deriche: Geodesic active regions and level set methods for supervised texture segmentation: Int. J. of Computer Vision, 46(3):223-247, 2002 Level set implementations of the Mumford-Shah functional were independently proposed by Chan and Vese; and by Tsai et al. See D. Mumford and J. Shah: Optimal approximations by piecewise smooth functions and associated variational problems: Comm. Pure Appl. Math., 42:577-685, 1989; T. Chan and L. Vese: Active contours without edges: IEEE Trans. Image Processing, 10(2):266-277, 2001; and A. Tsai, A. Yezzi, W. Wells, C. Tempany, D. Tucker, A. Fan, E. Grimson, and A. Willsky: Model-based curve evolution technique for image segmentation: In Comp. Vision Patt. Recog., pages 463-468, Kauai, Hi., 2001.
In contrast to other competitive segmentation methods such as graph cut approaches (see Boykov et al. and Shi et al. below), or the RandomWalker (see Grady et al. below), the level set method is based on a precise notion of a shape given by the representation in (1). See Y. Boykov, O. Veksler, and R. Zabih: Fast approximate energy minimization via graph cuts: IEEE T. on Patt. Anal. and Mach. Intell., 23(11):1222-1239, 2001; J. Shi and J. Malik: Normalized cuts and image segmentation: In Proc. IEEE Conf. on Comp. Vision Patt. Recog. (CVPR'97), San Juan, Puerto Rico, 1997; and L. Grady and G. Funka-Lea: Multi-label image segmentation for medical applications based on graph-theoretic electrical potentials: In M. Sonka, I. A. Kakadiaris, and J. Kybic, editors, Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis, number 3117 in LNCS, pages 230-245, Springer, 2004.
As a consequence, it is amenable to the introduction of statistical shape information which has been shown to drastically improve the segmentation of familiar objects in a given image. See M. Leventon, W. Grimson, and O. Faugeras: Statistical shape influence in geodesic active contours: In CVPR, volume 1, pages 316-323, Hilton Head Island, S.C., 2000; A. Tsai, A. J. Yezzi, and A. S. Willsky: Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification: IEEE Trans. on Image Processing, 10(8): 1169-1186, 2001; Y. Chen, H. Tagare, S. Thiruvenkadam, F. Huang, D. Wilson, K. S. Gopinath, R. W. Briggs, and E. Geiser: Using shape priors in geometric active contours in a variational framework: Int. J. of Computer Vision, 50(3):315-328, 2002; D. Cremers, S. J. Osher, and S. Soatto: Kernel density estimation and intrinsic alignment for knowledge-driven segmentation: Teaching level sets to walk: In C. E. Rasmussen, editor, Pattern Recognition, volume 3175 of LNCS, pages36-44. Springer, 2004; T. Riklin-Raviv, N. Kiryati, and N. Sochen: Unlevel sets: Geometry and prior-based segmentation: In T. Pajdla and V. Hlavac, editors, European Conf. on Comp. Vision, volume 3024 of LNCS, pages 50-61, Prague, 2004. Springer; D. Cremers, N. Sochen, and C. Schnorr: A multiphase dynamic labeling model for variational recognition-driven image segmentation: Int. J. of Computer Vision, 2005, To appear; and M. Rousson and D. Cremers: Efficient kernel density estimation of shape and intensity priors for level set segmentation: In MICCAI, volume 2, pages 757-764, 2005.
Various aspects relating to the background and field of the present invention are treated in a number of text-books, in addition to the publications mentioned herein in the course of the description of the present invention. For example, reference is made to the following text-books for useful background material: DIGITAL IMAGE PROCESSING, by Gonzalez and Woods, published by Prentice-Hall Inc., New Jersey, 2002; LEVEL SET METHODS AND FAST MARCHING METHODS, by J. A. Sethian, published by Cambridge University Press, 1996; 1999; IMAGE PROCESSING, ANALYSIS, AND MACHINE VISION, by Sonka, Hlavac, and Boyle, published by Brooks/Cole Publishing Company, Pacific Grove, Calif., 1999; and FUNDAMENTALS OF ELECTRONIC IMAGE PROCESSING, by A. R. Weeks, Jr., IEEE Press, New York, 1996; and various other text-books.